// 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

// 示例:

// 输入: n = 4, k = 2
// 输出:
// [
//   [2,4],
//   [3,4],
//   [2,3],
//   [1,2],
//   [1,3],
//   [1,4],
// ]

#include <vector>

using namespace std;

// 回溯法
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res{};
        if (n <= 0 || n < k) return res;
        vector<int> vec{};
        func(n, 1, k, vec, res);
        return res;
    }
    void func(int n, int index, int k, vector<int>& vec, vector<vector<int>>& res) {
        if (vec.size() == k) {
            res.push_back(vec);
            return;
        }
        for (int i = index; i <= n; ++i) {
            vec.push_back(i);
            func(n, i + 1, k, vec, res);
            vec.pop_back();
        }
    }
};

// 剪枝优化
class Solution1 {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res{};
        if (n <= 0 || n < k) return res;
        vector<int> vec{};
        func(n, 1, k, vec, res);
        return res;
    }
    void func(int n, int index, int k, vector<int>& vec, vector<vector<int>>& res) {
        if (vec.size() == k) {
            res.push_back(vec);
            return;
        }
        for (int i = index; i <= n - (k - vec.size()) + 1; ++i) {
            vec.push_back(i);
            func(n, i + 1, k, vec, res);
            vec.pop_back();
        }
    }
};

/* 回溯

*/
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res{};
        vector<int> vec{};
        backTrack(res, vec, n, 1, k);
        return res;
    }
    void backTrack(vector<vector<int>>& res, vector<int>& vec, const int& n, int i, const int& k) {
        if (vec.size() == k) {
            res.push_back(vec);
        } else {
            for (; i <= n; ++i) {
                vec.push_back(i);
                backTrack(res, vec, n, i + 1, k);
                vec.pop_back();
            }
        }
    }
};

/* 字典序（二进制）组合
*/
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res{};
        vector<int> vec(k + 1, 0);
        for (int i{1}; i <= k; ++i) { // vec初始化为1到k的整数序列
            vec[i - 1] = i;
        }
        vec[k] = n + 1; // 哨兵
        int j{0};
        while (j < k) {
            res.push_back(vector<int>(vec.begin(), vec.begin() + k)); // 前k个元素
            j = 0;
            while ((j < k) && (vec[j+1] == vec[j] + 1)) { // 找到第一个满足nums[j] + 1 != nums[j + 1] 的元素
                vec[j] = j + 1;
                ++j;
            }
            vec[j] = vec[j] + 1;
        }
        return res;
    }
};

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res{};
        vector<int> vec{};
        combine(1, n, 0, k, vec, res);
        return res;
    }
    void combine(int num, int n, int count, int k, vector<int> vec, vector<vector<int>>& res) {
        if (count == k) {
            res.push_back(vec);
            return;
        }
        for (int i{num}; i <= n; ++i) {
            vec.push_back(i);
            combine(i + 1, n, count + 1, k, vec, res);
            vec.pop_back();
        }
    }
};

/* 递归实现组合型枚举
从 n 个当中选 k 个的所有方案对应的枚举是组合型枚举
*/
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        dfs(1, n, k);
        return res;
    }
    void dfs(int cur, int n, int k) {
        // 剪枝：temp长度加上[cur,n]的长度小于k，不可能构造出长度为k的temp
        if (temp.size() + (n - cur + 1) < k) {
            return;
        }
        // 记录合法的答案
        if (temp.size() == k) {
            res.push_back(temp);
            return;
        }
        // 考虑选择当前位置
        temp.push_back(cur);
        dfs(cur + 1, n, k);
        temp.pop_back();
        // 考虑不选择当前位置
        dfs(cur + 1, n, k);
    }
private:
    vector<int> temp{};
    vector<vector<int>> res{};
};

/* 非递归（字典序）实现组合型枚举
n = 4, k = 2时：
temp数组:
1 2 5 
1 3 5 
2 3 5 
1 4 5 
2 4 5 
3 4 5 
*/
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        // 初始化
        // 将temp中的[0,k-1]每个位置设置为i+1，即[0,k-1]存[1-k]
        for (int i{1}; i <= k; ++i) {
            temp.push_back(i);
        }
        temp.push_back(n + 1); // 哨兵
        int j{0};
        while (j < k) {
            res.emplace_back(temp.begin(), temp.begin() + k);
            j = 0;
            // 寻找第一个temp[j] + 1 != temp[j+1] 的位置t
            // 我们需要把[0,t-1]区间内的每个位置重置成[1,t]
            while (j < k && temp[j] + 1 == temp[j + 1]) {
                temp[j] = j + 1;
                ++j;
            }
            // j是第一个temp[j]+1 != temp[j+1]的位置
            ++temp[j];
        }
        return res;
    }
private:
    vector<int> temp{};
    vector<vector<int>> res{};
};